#include <iostream>
#include <fstream>
#include <vector>
#include<functional>
#include<algorithm>
#include<vector>
#include <ctime>

template <typename Comparable>
void sort(vector<Comparable> & items);
template <typename Comparable>
void insertionsort(vector<Comparable> & items);
template <typename Comparable>
void quicksort(vector<Comparable> & items);


template <typename Comparable>
void insertionsort(vector<Comparable> & items)
{
	for (int p = 1; p < items.size(); ++p)
	{
		Comparable tmp = std::move(items[p]);

		int j;
		for (j = p; j > 0 && tmp < items[j - 1]; --j)
			items[j] = std::move(items[j - 1]);
		items[j] = std::move(tmp);
	}
};
float _myRand(int minValue, int maxValue)
{
	float Value = (rand() % (maxValue - minValue + 1)) + minValue;
	return Value;
}
template <typename Comparable>
void quicksort(vector<Comparable> & items)
{
	
	if(items.size()>1)
	{
		vector<Comparable> smaller;
		vector<Comparable> same;
		vector<Comparable> larger;

		int k = _myRand(ceil(items.size() / 3), floor(2*items.size() / 3));
		auto pivot = items[k];//实现选取元素随机生成并位于中间1/3的位置。
		//cout << pivot << endl << endl;


		for (auto & i : items)
		{
			if (i < pivot)
				smaller.push_back(std::move(i));
			else if (pivot < i)
				larger.push_back(std::move(i));
			else
				same.push_back(std::move(i));
		}
		quicksort(smaller);
		quicksort(larger);

		std::move(begin(smaller), end(smaller), begin(items));
		std::move(begin(same), end(same), begin(items) + smaller.size());
		std::move(begin(larger), end(larger), end(items) - larger.size());

	}
}
template <typename Comparable>
void sort(vector<Comparable> & items)
{
	if (items.size() <= 10)//长度小于10则使用插入排序。
	{
		insertionsort(items);
		cout << "because the length of vector is less than 10 ,we use insertion sort here." << endl;
		return;
	}
	else//大于10使用快速排序。
	{
		quicksort(items);
		return;
	}
}
